package 用队列实现栈;

import java.util.LinkedList;
import java.util.Queue;

/*
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 */
class MyStack {
    //建立两个队列,用来模拟实现栈
    Queue<Integer> queue1;
    Queue<Integer> queue2;
    //构造方法
    public MyStack() {
        //对queue1和queue2进行实例化
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    //入栈操作
    public void push(int x) {
        //关键逻辑就是对不为空的队列进行入队操作
        //如果两个队列都为空则默认是对queue1进行入队操作
        if (queue2.isEmpty()){
            queue1.offer(x);
        }else {
            queue2.offer(x);
        }
    }

    //出栈操作:
    //关键逻辑就是将不为空的队列里除了最后一个元素,全部转移到另一个空队列中
    //剩下的最后一个元素就是要出栈的元素
    public int pop() {
        //判断此时queue1与queue2哪个队列是空的,然后进行相应操作
        if (queue1.isEmpty()){
            //当就剩一个元素,就不用进行转移了,这个元素就是要出栈的元素
            while (queue2.size()!=1){
                queue1.offer(queue2.poll());
            }
            //此时queue2里剩的就是要出栈的元素
            return queue2.poll();
        }else {
            //当就剩一个元素,就不用进行转移了,这个元素就是要出栈的元素
            while (queue1.size()!=1){
                queue2.offer(queue1.poll());
            }
            //此时queue1里剩的就是要出栈的元素
            return queue1.poll();
        }
    }

    //获取栈顶元素:
    //逻辑和出栈逻辑类似,不过我们这里用临时变量ret记录一下
    //转移的最后一个元素值,记录完成还要把最后一个元素进行转移
    public int top() {
        //此时queue1里剩的就是要出栈的元素
        if (queue1.isEmpty()){
            while (queue2.size()!=1){
                queue1.offer(queue2.poll());
            }
            //记录最后一个元素值
            int ret = queue2.peek();
            //将最后一个元素进行转移
            queue1.offer(queue2.poll());
            //此时ret就是栈顶元素
            return ret;
        }else {
            while (queue1.size()!=1){
                queue2.offer(queue1.poll());
            }
            //记录最后一个元素值
            int ret = queue1.peek();
            //将最后一个元素进行转移
            queue2.offer(queue1.poll());
            //此时ret就是栈顶元素
            return ret;
        }
    }

    //对栈进行判空操作
    public boolean empty() {
        //当queue1与queue2都为空,说明模拟实现的栈为空
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
